package bintree.heap;

import java.util.Random;

/**
 * 测试100w个随机数插入最大堆并取出，判断元素是否有序(降序排列)
 * @author yuisama
 * @date 2021/12/10 16:28
 **/
public class HeapTest {
    public static void main(String[] args) {
//        int n = 1000000;
//        Random random = new Random();
//        MaxHeap maxHeap = new MaxHeap();
//        for (int i = 0; i < n; i++) {
//            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
//        }
//        int[] data = new int[n];
//        for (int i = 0; i < n; i++) {
//            data[i] = maxHeap.extractMax();
//        }
//        // 判断data是否是一个降序数组
//        for (int i = 0; i < data.length - 1; i++) {
//            if (data[i] < data[i + 1]) {
//                throw new RuntimeException("heap is error!");
//            }
//        }
//        System.out.println("max heap is complete true!");
        int n = 1000;
        // 先生成一个100w的随机数组
        Integer[] data = new Integer[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            data[i] = random.nextInt(1000000);
        }
        // 通过heapify将数组转为堆
        MinHeap<Integer> heap = new MinHeap<>(data);
        // 判断堆是否建成功
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = heap.extractMin();
        }
        for (int i = 0; i < n - 1; i++) {
            if (ret[i] > ret[i + 1]) {
                System.out.println();
                throw new RuntimeException("heap is error!");
            }
        }
        System.out.println("heapify is complete!");
    }
}
